# 84/100 动态规划-单词拆分
# leetcode第139题: https://leetcode.cn/problems/word-break/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/25
from leetcode import test


def wordBreak(s: str, wordDict: list[str]) -> bool:
    n = len(s)
    len_set = set(map(lambda x: len(x), s))
    min_word_len = min(len_set)  # 最小的单词长度
    if n < min_word_len:
        return False

    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(min_word_len, n + 1):
        for j in range(i, -1, -1):
            substr = s[j: i]
            if substr in wordDict and dp[j]:
                dp[i] = True

    return dp[n]


if __name__ == '__main__':
    # 一个map()函数的测试
    s = ['a', 'bc', 'def']
    m = map(lambda x: len(x), s)
    print(min(list(m)))

    # 验证
    inp = [{"s": "leetcode", "wordDict": ["leet", "code"]}, {"s": "applepenapple", "wordDict": ["apple", "pen"]},
           {"s": "catsandog", "wordDict": ["cats", "dog", "sand", "and", "cat"]}, ]
    out = [True, True, False]

    test.test_function(wordBreak, inp, out)
